Внутри список в Python — это не расслабленный связанный список, а высокоструктурированный ArrayList. Основная правда заключается в том, что он занимает непрерывный блок адресов в памяти. Здесь хранится не сам объект, а ссылка на объект ссылка(на уровне языка Си это указатель). Такой подход обеспечивает единообразное управление разнородными данными: будь то трёхкомпонентные кортежи (RGB) или сложные ключи шифрования (Key), каждый из них занимает только фиксированный размер указателя.
Математика адресации и баланс производительности
- $O(1)$ случайный доступ: по формуле $\text{адрес элемента} = \text{начальный адрес} + \text{индекс} \times \text{размер}$ процессор может мгновенно определить положение.
- Средний анализ (амортизированный анализ): используя стратегию перераспределения, хотя одна вставка может быть $O(n)$, но $\text{общая стоимость} = n + \sum_{j=0}^{\lg n} 2^j = 3n$, что гарантирует среднюю производительность добавления $O(1)$.
- Ограничения вставки: как показано на рисунке 8-2, при вставке в любом месте необходимо сдвинуть все последующие указатели, что имеет сложность $O(n)$.
Сравнение алгоритмов
В отличие от индексации в ArrayList ($O(1)$), время выполнения операции поиска в пропускном списке (Skip List) составляет $O(\log n)$. А основой алгоритма RSA является алгоритм Евклида, центральная идея которого — $gcd(a,0)=a$. Все эти алгоритмы работают на этом ограниченном пространстве памяти.